package leetcode.dfs;

/**
 * @author : zx
 * @version V1.0
 */
public class 二叉搜索子树的最大值和 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    private int max = 0;

    public int maxSumBST(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return max;
    }

    private int dfs(TreeNode node) {
        boolean leftFlag = false;
        boolean rightFlag = false;
        int leftNum = 0;
        int rightNum = 0;
        if (node.left != null) {
            leftNum = dfs(node.left);
            if (leftNum != Integer.MIN_VALUE && node.left.val < node.val) {
                leftFlag = true;
            }
        } else {
            leftNum = 0;
            leftFlag = true;
        }
        if (node.right != null) {
            rightNum = dfs(node.right);
            if (rightNum != Integer.MIN_VALUE && node.right.val > node.val) {
                rightFlag = true;
            }
        } else {
            rightNum = 0;
            rightFlag = true;
        }
        if (leftFlag && rightFlag) {
            int num = node.val + leftNum + rightNum;
            if (num > max) {
                max = num;
            }
            return num;
        } else {
            return Integer.MIN_VALUE;
        }
    }
}
